This invention relates to the interpolation of correction factors used for points between discrete correction sample points such as a matrix of points in an array or a series of spaced points along a line. Correction factors for particular data points are determined by preprocessing the correction factor data from weighted sector data leading and trailing the sector in which a particular point is located. This preprocessing modifies the correction factors input into a second order piecewise interpolation process for the sector of the particular point, and smoothly approximates an ideal correction curve using relatively few correction factors and minimal data processing operations. The invention is applicable, for example, to a digital convergence correction system that interpolates between points in a matrix of convergence correction points for a color CRT display, or image data that is up-converted, or time-domain sampled audio signals.
For the purposes of convergence control, the active scan area of a display screen may be divided into a matrix of rows and columns having factors corresponding to spaced points on the display. The number of rows and columns, and the number of resulting sections, are selected depending on the desired precision of correction. At each grid point in the matrix, a correction value is determined empirically by superimposing the red, green and blue rasters at that point, and noting the correction values that cancel any distortion and precisely align the rasters at that point. The value for each raster at each matrix point is stored, for example in a memory. The successive correction points in a line across the display are intended to represent the ideal correction curve. To effect correction, the values of the points on the curve are read out during display of the rasters, generally in successive horizontal lines, for example using a digital to analog converter coupled to drive correction coils that adjust the positions of the CRT electron beams for each color.
The number of correction points is less than the number of sampling points employed in reading out the correction factors. Therefore the correction points in the matrix can only approximate the ideal correction curve. An interpolation is performed in the horizontal and vertical directions to define additional values for the sampling points located between the stored values of the correction matrix. The correction curve should pass smoothly through adjacent correction values to avoid abrupt changes in the slope of the correction curve across the display, which cause undesirable visible bands in the display. Interpolation in the horizontal direction may be performed, for example, by low pass filtering the correction signal from the digital to analog converter, or by FIR filters.
In a vertical direction (or other direction), interpolation may be accomplished using computations to fit a low-order polynomial curve to a set of adjustment points. The adjustment points are defined or modified to provide a smooth and continuous correction curve. The calculations needed for such an interpolation function can be numerous, complex and memory intensive. A computation that forces the correction curve to progress linearly from one matrix adjustment value to the next may produce sharp inflections or changes in slope at the grid points. Sharp slope changes cause undesirable visual artifacts, referred to as xe2x80x9cbanding,xe2x80x9d that are visible as shade variations in the displayed picture. It is possible to process the correction curve values to limit the change in slope that will be permitted from point to point. This is a form of low pass filtering, and eliminates or attenuates some valid corrections that it would be advantageous to retain. This is particularly true for high bandwidth signals.
The problem of recovering an ideal signal such as a correction waveform from a succession of sample values is confronted in a variety of situations. If the number of samples is limited, it is not possible to identically recover all the frequency components of an input signal. Reading out the factors successively produces a stair-step signal. Linearly interpolating between the factors produces a varying sawtooth signal. Both corrections introduce high frequency components, namely abrupt slope changes that need to be filtered out using low pass filtering, which eliminates or attenuates valid higher frequency components.
For some applications the solution is to employ a larger number of factors or samples to define the waveform to be recovered. By sampling the waveform at a frequency higher than the Nyquist frequency the input waveform can be substantially recovered. Using a large number of sampling points or factors improves accuracy but is memory intensive. For other applications a computational filter such as a finite impulse response filter can be used. This solution requires computational resources and time for the filter to arrive at its best correction factors. It also introduces deviations from the original sampled data. Neither of these solutions is optimal. In such an application it may be desirable to minimize the number of factors that define the waveform and thereby to conserve memory. It is also desirable to avoid introducing high frequency components that correspond to abrupt changes in slope, and yet to obtain a relatively accurate representation of the input waveform wherein desirable slope changes are not unduly attenuated. These objectives should be achieved with a minimal computational burden in time and processing power.
An interpolation method in accordance with the inventive arrangements advantageously minimizes the number of factors that are needed to define the waveform and thereby to conserves memory. High frequency components that correspond to abrupt changes in slope are advantageously avoided, and yet, a relatively accurate representation of the input waveform is advantageously obtained wherein desirable slope changes are not unduly attenuated. Moreover, the problems of the prior art are advantageously achieved with a minimal computational burden in time and processing power.
A method for producing a plurality of successive output data values defining an output curve that approximates an input curve defined by a plurality of input sample values, output data values having a higher sampling frequency than the input sample values, in accordance with the inventive arrangements comprises the steps of: pre-emphasizing the plurality of input sample values; defining successive and overlapping intervals including at least three of the pre-emphasized input sample values; interpolating a plurality of the output data values in an interpolation interval by calculating a moving average of a linear interpolation curve based on the at least three pre-emphasized input sample values, each of the output data values being influenced by the at least three pre-emphasized input sample values; and, emphasizing differently the influence of the at least three pre-emphasized input sample values for determining different ones of the output data values in the interpolation interval, whereby the pre-emphasizing step brings the output curve controllably close to each of the input sample values and each incremental slope of the output curve varies smoothly between adjacent output data values.
The pre-emphasizing step can comprise the steps of: generating sampling factors based on the input sample values; and, using the sampling factors in the interpolating step.
The method can comprise the step of generating the sampling factors based on exactly three of the input sample values, whereby the output curve approximates the input curve within a precision of approximately 6%.
The method can comprise the step of generating the sampling factors based on at least five of the input sample values, whereby the output curve approximates the input curve within a precision at least approximately 1%.
The method can comprise the step of generating the sampling factors based on at least seven of the input sample values, whereby the output curve approximates the input curve within a precision at least approximately 0.1%.
The emphasizing step can comprise the steps of: ordering the pre-emphasized input sample values in each the interval such that a given one of the pre-emphasized input samples is preceded by a pre-emphasized input sample value and followed by a trailing pre-emphasized input sample value; emphasizing the influence of the preceding pre-emphasized input sample value when calculating the output data values preceding the given pre-emphasized input sample value; and, emphasizing the influence of the following pre-emphasized input sample value when calculating the output data values following the given pre-emphasized input sample value.
The method can comprise the step of shifting the interpolation interval by a selected number of the output data samples.
The method can further comprise the steps of: selecting the averaging interval to be an even number P of the interpolation intervals; and, selecting a value for P such that 2*P is a factor of two.
The interpolating step can comprises the step of using a ramp function for calculating incremental slopes preceding and following each the interpolation interval, the ramp function determining a smooth transition between adjacent ones of the interpolation intervals. The using a ramp function can comprise the steps of: calculating a first mean value based on the input sample values preceding each the interpolation interval; and, calculating a second mean value based on the input sample values following each the interpolation interval.
The pre-emphasizing step can comprise the steps of: defining successive and overlapping pre-emphasis intervals including at least three of the input sample values; and, successively pre-emphasizing a given input sample value in each the pre-emphasis interval, based on preceding and following ones of the input sample values in each the pre-emphasis interval.
Another method for producing a plurality of successive output data values defining an output curve that approximates an input curve defined by a plurality of input sample values, the output data values having a higher sampling frequency than the input sample values, in accordance with the inventive arrangements, comprises the steps of: defining successive and overlapping pre-emphasis intervals including at least three of the input sample values; successively pre-emphasizing a given input sample value in each the pre-emphasis interval, based on preceding and following ones of the input sample values in each the pre-emphasis interval; defining successive and overlapping interpolation intervals including a plurality of the pre-emphasized input sample values; interpolating a plurality of the output data values in an interpolation interval such that each incremental slope of the correction curve between adjacent output data values varies smoothly and the plurality of input sample values do not lie on the correction curve; and, adjusting the input sample values to control convergence correction, whereby the output curve closely approximates the input curve without banding artifacts.
The pre-emphasizing step can comprise the steps of: generating sampling factors based on the input sample values; and, using the sampling factors in the interpolating step.
The method can comprise the step of including exactly three of the input sample values in each the pre-emphasis interval, whereby the output curve approximates the input curve within a precision of approximately 6%.
The method can comprise the step of including at least five of the input sample values in each the pre-emphasis interval, whereby the output curve approximates the input curve within a precision of at least approximately 1%.
The method can comprise the step of including at least seven of the input sample values in each the pre-emphasis interval, whereby the output curve approximates the input curve within a precision of at least approximately 0.1%.
The emphasizing step can comprise the steps of: ordering the pre-emphasized input sample values in each the interval such that a given one of the pre-emphasized input samples is preceded by a pre-emphasized input sample value and followed by a trailing pre-emphasized input sample value; emphasizing the influence of the preceding pre-emphasized input sample value when calculating the output data values preceding the given pre-emphasized input sample value; and, emphasizing the influence of the following pre-emphasized input sample value when calculating the output data values following the given pre-emphasized input sample value.
The method can comprising the further step of shifting the interpolation interval by a selected number of the output data samples.
The method can also comprise the steps of: selecting the averaging interval to be an even number P of the interpolation intervals; and, selecting a value for P such that 2*P is a factor of two.
The interpolating step can comprises the step of using a ramp function for calculating incremental slopes preceding and following each the interpolation interval, the ramp function determining a smooth transition between adjacent ones of the interpolation intervals. The using a ramp function step can comprise the steps of: calculating a first mean value based on the input sample values preceding each the interpolation interval; and, calculating a second mean value based on the input sample values following each the interpolation interval.